//Z字形变换--优化：O(n)空间复杂度的算法
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.size();
        if(numRows == 1)
        {
            return s;
        }
        int d = 2*numRows-2;//公差
        string ret;
        for(size_t i = 0 ; i < numRows ; i++)
        {
            if(i == 0 || i == numRows-1)
            {
                //第一行和最后一行
                int pos = i;
                for(;pos < n ;)
                {
                    ret += s[pos];
                    pos += d;
                }
            }
            else 
            {
                int pos1 = i;
                int pos2 = d-i;
                while(pos1 < n || pos2 < n)
                {
                    if(pos1 < n) ret += s[pos1];
                    if(pos2 < n) ret += s[pos2];
                    pos1 += d;
                    pos2 += d;
                }

            }
        }
        return ret;
    }
};

//外观数列
class Solution {
public:
    string countAndSay(int n) {
        string prev = "1";
        for (size_t i = 2; i <= n; ++i)
        {
            string temp;
            int left = 0, right = 1;
            while (right < prev.size())
            {
                if (prev[right] == prev[left])
                {
                    ++right;
                }
                else
                {
                    int count = right - left;
                    temp += (to_string(count) + to_string(prev[left] - '0'));
                    left = right;
                }

            }
            temp += to_string(right - left) + to_string(prev[left] - '0');

            prev = temp;
        }
        return prev;
    }
};

//数青蛙
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        vector<int> hash(5);
        //0：c
        //1：r
        //2：o
        //3：a
        //4：k
        for(size_t i = 0 ; i < croakOfFrogs.size() ; ++i)
        {
            if(croakOfFrogs[i] == 'c')
            {
                if(hash[4] > 0)
                {
                    --hash[4];
                }
                ++hash[0];

            }
            else if(croakOfFrogs[i] == 'r')
            {
                if(hash[0] > 0) hash[0]--,hash[1]++;
                else return -1;
            }
            else if(croakOfFrogs[i] == 'o')
            {
                if(hash[1] > 0) hash[1]--,hash[2]++;
                else return -1;
            }
            else if(croakOfFrogs[i] == 'a')
            {
                if(hash[2] > 0) hash[2]--,hash[3]++;
                else return -1;
            }
            else if(croakOfFrogs[i] == 'k')
            {
                if(hash[3] > 0) hash[3]--,hash[4]++;
                else return -1;
            }
            else 
            {
                return -1;
            }
        }
        for(size_t i = 0 ; i < 4 ; ++i)
        {
            if(hash[i] > 0) return -1;
        }
        return hash[4];
    }
};



